﻿//https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        int count = 0;
        int left = 0, right = n - 1, leftmax = 0, rightmax = 0;
        while (left < right)
        {
            leftmax = max(leftmax, height[left]);
            rightmax = max(rightmax, height[right]);
            if (leftmax < rightmax)
            {
                count += leftmax - height[left];
                left++;
            }
            else
            {
                count += rightmax - height[right];
                right--;
            }
        }

        return count;
    }
};